package com.sheng.leetcode.year2023.month12.day11;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/12/11
 * <p>
 * 1631. 最小体力消耗路径<p>
 * <p>
 * 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，<p>
 * 其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，<p>
 * 且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。<p>
 * 你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。<p>
 * 一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。<p>
 * 请你返回从左上角走到右下角的最小 体力消耗值 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：heights = [[1,2,2],[3,8,2],[5,3,5]]<p>
 * 输出：2<p>
 * 解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。<p>
 * 这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：heights = [[1,2,3],[3,8,4],[5,3,5]]<p>
 * 输出：1<p>
 * 解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。<p>
 * <p>
 * 示例 3：<p>
 * 输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]<p>
 * 输出：0<p>
 * 解释：上图所示路径不需要消耗任何体力。<p>
 * <p>
 * 提示：<p>
 * rows == heights.length<p>
 * columns == heights[i].length<p>
 * 1 <= rows, columns <= 100<p>
 * 1 <= heights[i][j] <= 10^6<p>
 */
public class LeetCode1631 {

    @Test
    public void test01() {
//        int[][] heights = {{1, 2, 2}, {3, 8, 2}, {5, 3, 5}};
//        int[][] heights = {{1, 2, 3}, {3, 8, 4}, {5, 3, 5}};
//        int[][] heights = {{1, 2, 1, 1, 1}, {1, 2, 1, 2, 1}, {1, 2, 1, 2, 1}, {1, 2, 1, 2, 1}, {1, 1, 1, 2, 1}};
        int[][] heights = {{4, 3, 4, 10, 5, 5, 9, 2}, {10, 8, 2, 10, 9, 7, 5, 6}, {5, 8, 10, 10, 10, 7, 4, 2}, {5, 1, 3, 1, 1, 3, 1, 9}, {6, 4, 10, 6, 10, 9, 4, 6}};
        System.out.println(new Solution().minimumEffortPath(heights));
    }
}

class Solution {

    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int rows, columns;

    int[][] heights;

    public int minimumEffortPath(int[][] heights) {
        // 求整个路径上相邻的两个数的最大差值的绝对值
        rows = heights.length;
        columns = heights[0].length;
        this.heights = heights;
        // 二分查找最小消耗的体力值
        int left = 0, right = 1000000;
        while (left < right) {
            int mid = (left + right) / 2;
            if (dfs(0, 0, mid, new boolean[rows][columns])) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public Boolean dfs(int x, int y, int min, boolean[][] flag) {
        // 判断是否到达最后节点
        if (x == rows - 1 && y == columns - 1) {
            return true;
        }
        flag[x][y] = true;
        for (int[] direction : directions) {
            int i = direction[0] + x;
            int j = direction[1] + y;
            // 判断下一步是否合理，以及下一步是否重复走过
            if (i >= 0 && i < rows && j >= 0 && j < columns && !flag[i][j]) {
                // 执行下一步
                int abs = Math.abs(heights[x][y] - heights[i][j]);
                // 判断下一步是否超过当前体力最大值
                if (abs <= min && dfs(i, j, min, flag)) {
                    return true;
                }
            }
        }
        return false;
    }
}
